// list standard header
#pragma once
#ifndef _LIST_
#define _LIST_
#ifndef RC_INVOKED
#include <xmemory>

#if _HAS_CXX17
#include <xpolymorphic_allocator.h>
#endif // _HAS_CXX17

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new

_STD_BEGIN
// CLASS TEMPLATE _List_unchecked_const_iterator
template <class _Mylist,
    class _Base = _Iterator_base0>
class _List_unchecked_const_iterator : public _Base { // unchecked iterator for nonmutable list
public:
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mylist::_Nodeptr;
    using value_type      = typename _Mylist::value_type;
    using difference_type = typename _Mylist::difference_type;
    using pointer         = typename _Mylist::const_pointer;
    using reference       = const value_type&;

    _List_unchecked_const_iterator() : _Ptr() { // construct with null node pointer
    }

    _List_unchecked_const_iterator(_Nodeptr _Pnode, const _Mylist* _Plist)
        : _Ptr(_Pnode) { // construct with node pointer _Pnode
        this->_Adopt(_Plist);
    }

    _NODISCARD reference operator*() const { // return designated value
        return _Ptr->_Myval;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _List_unchecked_const_iterator& operator++() { // preincrement
        _Ptr = _Ptr->_Next;
        return *this;
    }

    _List_unchecked_const_iterator operator++(int) { // postincrement
        _List_unchecked_const_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _List_unchecked_const_iterator& operator--() { // predecrement
        _Ptr = _Ptr->_Prev;
        return *this;
    }

    _List_unchecked_const_iterator operator--(int) { // postdecrement
        _List_unchecked_const_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    _NODISCARD bool operator==(const _List_unchecked_const_iterator& _Right) const { // test for iterator equality
        return _Ptr == _Right._Ptr;
    }

    _NODISCARD bool operator!=(const _List_unchecked_const_iterator& _Right) const { // test for iterator inequality
        return !(*this == _Right);
    }

    _Nodeptr _Ptr; // pointer to node
};

// CLASS TEMPLATE _List_unchecked_iterator
template <class _Mylist>
class _List_unchecked_iterator : public _List_unchecked_const_iterator<_Mylist> { // unchecked iterator for mutable list
public:
    using _Mybase           = _List_unchecked_const_iterator<_Mylist>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mylist::_Nodeptr;
    using value_type      = typename _Mylist::value_type;
    using difference_type = typename _Mylist::difference_type;
    using pointer         = typename _Mylist::pointer;
    using reference       = value_type&;

    _List_unchecked_iterator() { // construct with null node
    }

    _List_unchecked_iterator(_Nodeptr _Pnode, const _Mylist* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
        return (reference) * *(_Mybase*) this;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _List_unchecked_iterator& operator++() { // preincrement
        ++(*(_Mybase*) this);
        return *this;
    }

    _List_unchecked_iterator operator++(int) { // postincrement
        _List_unchecked_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _List_unchecked_iterator& operator--() { // predecrement
        --(*(_Mybase*) this);
        return *this;
    }

    _List_unchecked_iterator operator--(int) { // postdecrement
        _List_unchecked_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }
};

// CLASS TEMPLATE _List_const_iterator
template <class _Mylist>
class _List_const_iterator
    : public _List_unchecked_const_iterator<_Mylist, _Iterator_base> { // iterator for nonmutable list
public:
    using _Mybase           = _List_unchecked_const_iterator<_Mylist, _Iterator_base>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mylist::_Nodeptr;
    using value_type      = typename _Mylist::value_type;
    using difference_type = typename _Mylist::difference_type;
    using pointer         = typename _Mylist::const_pointer;
    using reference       = const value_type&;

    _List_const_iterator() : _Mybase() { // construct with null node pointer
    }

    _List_const_iterator(_Nodeptr _Pnode, const _Mylist* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
#if _ITERATOR_DEBUG_LEVEL != 0
        const auto _Mycont = static_cast<const _Mylist*>(this->_Getcont());
        _STL_ASSERT(_Mycont, "cannot dereference value-initialized list iterator");
        _STL_VERIFY(this->_Ptr != _Mycont->_Myhead, "cannot dereference end list iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return this->_Ptr->_Myval;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _List_const_iterator& operator++() { // preincrement
#if _ITERATOR_DEBUG_LEVEL != 0
        const auto _Mycont = static_cast<const _Mylist*>(this->_Getcont());
        _STL_ASSERT(_Mycont, "cannot increment value-initialized list iterator");
        _STL_VERIFY(this->_Ptr != _Mycont->_Myhead, "cannot increment end list iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        this->_Ptr = this->_Ptr->_Next;
        return *this;
    }

    _List_const_iterator operator++(int) { // postincrement
        _List_const_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _List_const_iterator& operator--() { // predecrement
        const auto _New_ptr = this->_Ptr->_Prev;
#if _ITERATOR_DEBUG_LEVEL != 0
        const auto _Mycont = static_cast<const _Mylist*>(this->_Getcont());
        _STL_ASSERT(_Mycont, "cannot decrement value-initialized list iterator");
        _STL_VERIFY(_New_ptr != _Mycont->_Myhead, "cannot decrement begin list iterator");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        this->_Ptr = _New_ptr;
        return *this;
    }

    _List_const_iterator operator--(int) { // postdecrement
        _List_const_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    _NODISCARD bool operator==(const _List_const_iterator& _Right) const { // test for iterator equality
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(this->_Getcont() == _Right._Getcont(), "list iterators incompatible");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        return this->_Ptr == _Right._Ptr;
    }

    _NODISCARD bool operator!=(const _List_const_iterator& _Right) const { // test for iterator inequality
        return !(*this == _Right);
    }

#if _ITERATOR_DEBUG_LEVEL != 0
    friend void _Verify_range(const _List_const_iterator& _First, const _List_const_iterator& _Last) {
        _STL_VERIFY(_First._Getcont() == _Last._Getcont(), "list iterators in range are from different containers");
    }
#endif // _ITERATOR_DEBUG_LEVEL != 0

    using _Prevent_inheriting_unwrap = _List_const_iterator;

    _NODISCARD _List_unchecked_const_iterator<_Mylist> _Unwrapped() const {
        return _List_unchecked_const_iterator<_Mylist>(this->_Ptr, static_cast<const _Mylist*>(this->_Getcont()));
    }

    void _Seek_to(const _List_unchecked_const_iterator<_Mylist> _It) {
        this->_Ptr = _It._Ptr;
    }
};

// CLASS TEMPLATE _List_iterator
template <class _Mylist>
class _List_iterator : public _List_const_iterator<_Mylist> { // iterator for mutable list
public:
    using _Mybase           = _List_const_iterator<_Mylist>;
    using iterator_category = bidirectional_iterator_tag;

    using _Nodeptr        = typename _Mylist::_Nodeptr;
    using value_type      = typename _Mylist::value_type;
    using difference_type = typename _Mylist::difference_type;
    using pointer         = typename _Mylist::pointer;
    using reference       = value_type&;

    _List_iterator() { // construct with null node
    }

    _List_iterator(_Nodeptr _Pnode, const _Mylist* _Plist)
        : _Mybase(_Pnode, _Plist) { // construct with node pointer _Pnode
    }

    _NODISCARD reference operator*() const { // return designated value
        return (reference) * *(_Mybase*) this;
    }

    _NODISCARD pointer operator->() const { // return pointer to class object
        return pointer_traits<pointer>::pointer_to(**this);
    }

    _List_iterator& operator++() { // preincrement
        ++(*(_Mybase*) this);
        return *this;
    }

    _List_iterator operator++(int) { // postincrement
        _List_iterator _Tmp = *this;
        ++*this;
        return _Tmp;
    }

    _List_iterator& operator--() { // predecrement
        --(*(_Mybase*) this);
        return *this;
    }

    _List_iterator operator--(int) { // postdecrement
        _List_iterator _Tmp = *this;
        --*this;
        return _Tmp;
    }

    using _Prevent_inheriting_unwrap = _List_iterator;

    _NODISCARD _List_unchecked_iterator<_Mylist> _Unwrapped() const {
        return _List_unchecked_iterator<_Mylist>(this->_Ptr, static_cast<const _Mylist*>(this->_Getcont()));
    }
};

// list TYPE WRAPPERS
template <class _Value_type, class _Size_type, class _Difference_type, class _Pointer, class _Const_pointer,
    class _Reference, class _Const_reference, class _Nodeptr_type>
struct _List_iter_types { // wraps types needed by iterators
    using value_type      = _Value_type;
    using size_type       = _Size_type;
    using difference_type = _Difference_type;
    using pointer         = _Pointer;
    using const_pointer   = _Const_pointer;
    using _Nodeptr        = _Nodeptr_type;
};

template <class _Value_type, class _Voidptr>
struct _List_node { // list node
    using value_type = _Value_type;
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _List_node>;
    _Nodeptr _Next; // successor node, or first element if head
    _Nodeptr _Prev; // predecessor node, or last element if head
    _Value_type _Myval; // the stored value, unused if head

    _List_node(const _List_node&) = delete;
    _List_node& operator=(const _List_node&) = delete;

    template <class _Alnode>
    static _Nodeptr _Buyheadnode(_Alnode& _Al) noexcept {
        // assumes construction of pointer does not throw:
        auto _Result = _Al.allocate(1);
        allocator_traits<_Alnode>::construct(_Al, _STD addressof(_Result->_Next), _Result);
        allocator_traits<_Alnode>::construct(_Al, _STD addressof(_Result->_Prev), _Result);
        return _Result;
    }

    template <class _Alnode>
    static void _Freenode0(
        _Alnode& _Al, _Nodeptr _Ptr) noexcept { // destroy pointer members in _Ptr and deallocate with _Al
        static_assert(is_same_v<typename _Alnode::value_type, _List_node>, "Bad _Freenode0 call");
        using _Alnode_traits = allocator_traits<_Alnode>;
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Next));
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Prev));
        _Alnode_traits::deallocate(_Al, _Ptr, 1);
    }

    template <class _Alnode>
    static void _Freenode(_Alnode& _Al, _Nodeptr _Ptr) noexcept { // destroy all members in _Ptr and deallocate with _Al
        using _Alnode_traits = allocator_traits<_Alnode>;
        _Alnode_traits::destroy(_Al, _STD addressof(_Ptr->_Myval));
        _Freenode0(_Al, _Ptr);
    }

    template <class _Alnode>
    static void _Free_non_head(
        _Alnode& _Al, _Nodeptr _Head) noexcept { // free a list starting at _First and terminated at nullptr
        _Head->_Prev->_Next = nullptr;

        auto _Pnode = _Head->_Next;
        for (_Nodeptr _Pnext; _Pnode != nullptr; _Pnode = _Pnext) {
            _Pnext = _Pnode->_Next;
            _Freenode(_Al, _Pnode);
        }
    }
};

template <class _Ty>
struct _List_simple_types : public _Simple_types<_Ty> { // wraps types needed by iterators
    using _Node    = _List_node<_Ty, void*>;
    using _Nodeptr = _Node*;
};

// CLASS TEMPLATE _List_val
template <class _Val_types>
class _List_val : public _Container_base { // base class for list to hold data
public:
    using _Nodeptr = typename _Val_types::_Nodeptr;

    using value_type      = typename _Val_types::value_type;
    using size_type       = typename _Val_types::size_type;
    using difference_type = typename _Val_types::difference_type;
    using pointer         = typename _Val_types::pointer;
    using const_pointer   = typename _Val_types::const_pointer;
    using reference       = value_type&;
    using const_reference = const value_type&;

    _List_val() : _Myhead(), _Mysize(0) { // initialize data
    }

    _Nodeptr _Myhead; // pointer to head node
    size_type _Mysize; // number of elements
};

// STRUCT TEMPLATE _List_node_emplace_op
enum class _Allocation_strategy { _Preallocated, _On_demand };

template <class _Alnode, _Allocation_strategy _Strategy>
struct _List_node_emplace_op {
    using _Alnode_traits = allocator_traits<_Alnode>;
    using pointer        = typename _Alnode_traits::pointer;
    using size_type      = typename _Alnode_traits::size_type;
    using value_type     = typename _Alnode_traits::value_type;

    explicit _List_node_emplace_op(_Alnode& _Al_) : _Al(_Al_), _To_insert() {}

    ~_List_node_emplace_op() {
        if (_To_insert) {
            _Alnode_traits::destroy(_Al, _STD addressof(_To_insert->_Myval));
            _Al.deallocate(_To_insert, 1);
        }
    }

    _List_node_emplace_op(const _List_node_emplace_op&) = delete;
    _List_node_emplace_op& operator=(const _List_node_emplace_op&) = delete;

    template <class... _Valty>
    typename value_type::value_type& _Allocate(_Valty&&... _Val) {
        _STL_INTERNAL_CHECK(!_To_insert);
        _Alloc_construct_ptr<_Alnode> _Newnode(_Al);
        _Newnode._Allocate(); // throws
        _Alnode_traits::construct(_Newnode._Al, _STD addressof(_Newnode._Ptr->_Myval), _STD forward<_Valty>(_Val)...);
        _To_insert = _Newnode._Release();
        return _To_insert->_Myval;
    }

    // TRANSITION, if constexpr
    template <class _Valty, _Allocation_strategy _Strategy2 = _Strategy,
        enable_if_t<_Strategy2 == _Allocation_strategy::_On_demand, int> = 0>
    typename value_type::value_type& _Allocate_if_necessary(_Valty&& _Val) {
        if (!_To_insert) {
            _Allocate(_STD forward<_Valty>(_Val));
        }

        return _To_insert->_Myval;
    }

    template <class _Valty, _Allocation_strategy _Strategy2 = _Strategy,
        enable_if_t<_Strategy2 == _Allocation_strategy::_Preallocated, int> = 0>
    typename value_type::value_type& _Allocate_if_necessary(_Valty&&) const noexcept {
        return _To_insert->_Myval;
    }

    pointer _Transfer_before(const pointer _Rightnode) noexcept {
        _STL_INTERNAL_CHECK(_To_insert != pointer());
        const pointer _Leftnode = _Rightnode->_Prev;
        _Alnode_traits::construct(_Al, _STD addressof(_To_insert->_Next), _Rightnode);
        _Alnode_traits::construct(_Al, _STD addressof(_To_insert->_Prev), _Leftnode);
        _Rightnode->_Prev = _To_insert;
        _Leftnode->_Next  = _To_insert;
        return _STD exchange(_To_insert, pointer());
    }

    _Alnode& _Al;
    pointer _To_insert; // if not nullptr, _To_insert->_Myval is constructed
};

// STRUCT TEMPLATE _List_node_insert_op
template <class _Alnode>
struct _List_node_insert_op {
    // list insert operation which maintains exception safety
    using _Alnode_traits = allocator_traits<_Alnode>;
    using pointer        = typename _Alnode_traits::pointer;
    using size_type      = typename _Alnode_traits::size_type;
    using value_type     = typename _Alnode_traits::value_type;

    explicit _List_node_insert_op(_Alnode& _Al_)
        : _Al(_Al_), _Tail(pointer_traits<pointer>::pointer_to(_Base)), _Added(0) {}

    _List_node_insert_op(const _List_node_insert_op&) = delete;
    _List_node_insert_op& operator=(const _List_node_insert_op&) = delete;

    template <class... _CArgT>
    void _Append_n(size_type _Count, const _CArgT&... _Carg) {
        // Append _Count Ts constructed from _Carg to this insert operation.
        _Alloc_construct_ptr<_Alnode> _Newnode(_Al);
        for (; 0 < _Count; --_Count) {
            _Newnode._Allocate(); // throws
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Myval), _Carg...); // throws
            _Alnode_traits::construct(_Al, _STD addressof(_Tail->_Next), _Newnode._Ptr); // assumed nothrow
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Prev), _Tail); // assumed nothrow
            _Tail = _Newnode._Ptr;
            ++_Added;
        }

        (void) _Newnode._Release();
    }

    template <class _InIt, class _Sentinel>
    void _Append_range_unchecked(_InIt _First, const _Sentinel _Last) {
        // Append new elements constructed from [_First, _Last) to this insert operation.
        _Alloc_construct_ptr<_Alnode> _Newnode(_Al);
        for (; _First != _Last; ++_First) {
            _Newnode._Allocate(); // throws
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Myval), *_First); // throws
            _Alnode_traits::construct(_Al, _STD addressof(_Tail->_Next), _Newnode._Ptr); // assumed nothrow
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Prev), _Tail); // assumed nothrow
            _Tail = _Newnode._Ptr;
            ++_Added;
        }

        (void) _Newnode._Release();
    }

    template <class _Val_types>
    pointer _Attach_before(_List_val<_Val_types>& _My_data, const pointer _Insert_before) noexcept {
        // Attach the elements in this insert operation before _Insert_before.
        // If no elements were inserted, returns _Insert_before; otherwise returns a pointer
        // to the first inserted list node.
        // Resets *this to be empty.
        if (_Added == 0) {
            return _Insert_before;
        }

        _My_data._Mysize += _STD exchange(_Added, size_type{0});

        _Alnode_traits::construct(_Al, _STD addressof(_Tail->_Next), _Insert_before); // assumed nothrow
        const auto _Insert_after = _STD exchange(_Insert_before->_Prev, _Tail);

        const auto _First_inserted = _Base._Next;
        _Insert_after->_Next       = _First_inserted;
        _First_inserted->_Prev     = _Insert_after;

        _Alnode_traits::destroy(_Al, _STD addressof(_Base._Next));
        _Tail = pointer_traits<pointer>::pointer_to(_Base);
        return _First_inserted;
    }

    template <class _Val_types>
    void _Attach_at_end(_List_val<_Val_types>& _My_data) noexcept {
        _Attach_before(_My_data, _My_data._Myhead);
    }

    template <class _Val_types>
    void _Attach_head(_List_val<_Val_types>& _My_data) {
        _Alloc_construct_ptr<_Alnode> _Newnode(_Al);
        _Newnode._Allocate(); // throws, assumed nothrow hereafter
        if (_Added == 0) {
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Next), _Newnode._Ptr);
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Prev), _Newnode._Ptr);
            _My_data._Mysize = 0;
        } else {
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Next), _Base._Next);
            _Alnode_traits::construct(_Al, _STD addressof(_Newnode._Ptr->_Prev), _Tail);
            _Base._Next->_Prev = _Newnode._Ptr;
            _Tail->_Next       = _Newnode._Ptr;
            _My_data._Mysize   = _STD exchange(_Added, size_type{0});
            _Alnode_traits::destroy(_Al, _STD addressof(_Tail->_Next));
            _Tail = pointer_traits<pointer>::pointer_to(_Base);
        }

        _My_data._Myhead = _Newnode._Release();
    }

    ~_List_node_insert_op() {
        if (_Added == 0) {
            return;
        }

        _Alnode_traits::construct(_Al, _STD addressof(_Tail->_Next), nullptr);
        pointer _Subject = _Base._Next;
        while (_Subject != nullptr) {
            value_type::_Freenode(_Al, _STD exchange(_Subject, _Subject->_Next));
        }

        _Alnode_traits::destroy(_Al, _STD addressof(_Base._Next));
    }

private:
    _Alnode& _Al;
    pointer _Tail; // points to the most recently appended element; it doesn't have _Next constructed
    size_type _Added;
    union {
        value_type _Base; // only ever uses _Next, other members not constructed
                          // _Next points to the first appended element
    };
};

// CLASS TEMPLATE list
template <class _Ty, class _Alloc = allocator<_Ty>>
class list { // bidirectional linked list
private:
    template <class>
    friend class _Hash;

    using _Alty          = _Rebind_alloc_t<_Alloc, _Ty>;
    using _Alty_traits   = allocator_traits<_Alty>;
    using _Node          = _List_node<_Ty, typename allocator_traits<_Alloc>::void_pointer>;
    using _Alnode        = _Rebind_alloc_t<_Alloc, _Node>;
    using _Alnode_traits = allocator_traits<_Alnode>;
    using _Nodeptr       = typename _Alnode_traits::pointer;

    using _Val_types = conditional_t<_Is_simple_alloc_v<_Alnode>, _List_simple_types<_Ty>,
        _List_iter_types<_Ty, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Ty&, const _Ty&, _Nodeptr>>;

    using _Scary_val = _List_val<_Val_types>;

public:
    static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
        _MISMATCHED_ALLOCATOR_MESSAGE("list<T, Allocator>", "T"));

    using value_type      = _Ty;
    using allocator_type  = _Alloc;
    using size_type       = typename _Alty_traits::size_type;
    using difference_type = typename _Alty_traits::difference_type;
    using pointer         = typename _Alty_traits::pointer;
    using const_pointer   = typename _Alty_traits::const_pointer;
    using reference       = value_type&;
    using const_reference = const value_type&;

    using iterator                  = _List_iterator<_Scary_val>;
    using const_iterator            = _List_const_iterator<_Scary_val>;
    using _Unchecked_iterator       = _List_unchecked_iterator<_Scary_val>;
    using _Unchecked_const_iterator = _List_unchecked_const_iterator<_Scary_val>;

    using reverse_iterator       = _STD reverse_iterator<iterator>;
    using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

    list() : _Mypair(_Zero_then_variadic_args_t()) { // construct empty list
        _Alloc_sentinel_and_proxy();
    }

    explicit list(const _Alloc& _Al) : _Mypair(_One_then_variadic_args_t(), _Al) { // construct empty list, allocator
        _Alloc_sentinel_and_proxy();
    }

private:
    template <class _Any_alloc>
    explicit list(_Move_allocator_tag, _Any_alloc& _Al) : _Mypair(_One_then_variadic_args_t(), _STD move(_Al)) {
        _Alloc_sentinel_and_proxy();
    }

    void _Construct_n(_CRT_GUARDOVERFLOW size_type _Count) {
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Get_data());
        _List_node_insert_op<_Alnode> _Appended(_Getal());
        _Appended._Append_n(_Count);
        _Appended._Attach_head(_Get_data());
        _Proxy._Release();
    }

public:
    explicit list(_CRT_GUARDOVERFLOW size_type _Count)
        : _Mypair(_Zero_then_variadic_args_t()) { // construct list from _Count * _Ty()
        _Construct_n(_Count);
    }

    explicit list(_CRT_GUARDOVERFLOW size_type _Count, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct list from _Count * _Ty(), with allocator
        _Construct_n(_Count);
    }

private:
    void _Construct_n(_CRT_GUARDOVERFLOW size_type _Count, const _Ty& _Val) {
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Get_data());
        _List_node_insert_op<_Alnode> _Appended(_Getal());
        _Appended._Append_n(_Count, _Val);
        _Appended._Attach_head(_Get_data());
        _Proxy._Release();
    }

public:
    list(_CRT_GUARDOVERFLOW size_type _Count, const _Ty& _Val)
        : _Mypair(_Zero_then_variadic_args_t()) { // construct list from _Count * _Val
        _Construct_n(_Count, _Val);
    }

    list(_CRT_GUARDOVERFLOW size_type _Count, const _Ty& _Val, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct list from _Count * _Val, allocator
        _Construct_n(_Count, _Val);
    }

private:
    template <class _Iter>
    void _Construct_range_unchecked(_Iter _First, _Iter _Last) {
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _Get_data());
        _List_node_insert_op<_Alnode> _Appended(_Getal());
        _Appended._Append_range_unchecked(_First, _Last);
        _Appended._Attach_head(_Get_data());
        _Proxy._Release();
    }

public:
    list(const list& _Right)
        : _Mypair(_One_then_variadic_args_t(), _Alnode_traits::select_on_container_copy_construction(
                                                   _Right._Getal())) { // construct list by copying _Right
        _Construct_range_unchecked(_Right._Unchecked_begin(), _Right._Unchecked_end());
    }

    list(const list& _Right, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct list by copying _Right, allocator
        _Construct_range_unchecked(_Right._Unchecked_begin(), _Right._Unchecked_end());
    }

    template <class _Iter, class = enable_if_t<_Is_iterator_v<_Iter>>>
    list(_Iter _First, _Iter _Last) : _Mypair(_Zero_then_variadic_args_t()) { // construct list from [_First, _Last)
        _Adl_verify_range(_First, _Last);
        _Construct_range_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last));
    }

    template <class _Iter, class = enable_if_t<_Is_iterator_v<_Iter>>>
    list(_Iter _First, _Iter _Last, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct list, allocator from [_First, _Last)
        _Adl_verify_range(_First, _Last);
        _Construct_range_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last));
    }

    list(list&& _Right)
        : _Mypair(_One_then_variadic_args_t(), _STD move(_Right._Getal())) { // construct list by moving _Right
        _Alloc_sentinel_and_proxy();
        _Swap_val(_Right);
    }

    list(list&& _Right, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct list by moving _Right, allocator
        if
            _CONSTEXPR_IF(!_Alnode_traits::is_always_equal::value) {
                if (_Getal() != _Right._Getal()) {
                    _Construct_range_unchecked(_STD make_move_iterator(_Right._Unchecked_begin()),
                        _STD make_move_iterator(_Right._Unchecked_end()));
                    return;
                }
            }

        _Alloc_sentinel_and_proxy();
        _Swap_val(_Right);
    }

private:
    void _Move_assign(list& _Right, _Equal_allocators) noexcept {
        clear();
        _Pocma(_Getal(), _Right._Getal());
        _Swap_val(_Right);
    }

    void _Move_assign(list& _Right, _Propagate_allocators) {
        if (_Getal() == _Right._Getal()) {
            _Move_assign(_Right, _Equal_allocators{});
        } else {
            auto&& _Alproxy       = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
            auto&& _Alproxy_right = _GET_PROXY_ALLOCATOR(_Alnode, _Right._Getal());
            _Container_proxy_ptr<_Alty> _Proxy(_Alproxy_right, _Leave_proxy_unbound{});
            auto& _My_data      = _Get_data();
            auto& _Right_data   = _Right._Get_data();
            const auto _Newhead = _STD exchange(_Right_data._Myhead, _Node::_Buyheadnode(_Right._Getal()));
            const auto _Newsize = _STD exchange(_Right_data._Mysize, size_type{0});
            _Tidy();
            _Pocma(_Getal(), _Right._Getal());
            _My_data._Myhead = _Newhead;
            _My_data._Mysize = _Newsize;
            _Proxy._Bind(_Alproxy, _STD addressof(_My_data));
            _My_data._Swap_proxy_and_iterators(_Right_data);
        }
    }

    void _Move_assign(list& _Right, _No_propagate_allocators) {
        if (_Getal() == _Right._Getal()) {
            _Move_assign(_Right, _Equal_allocators{});
        } else {
            assign(
                _STD make_move_iterator(_Right._Unchecked_begin()), _STD make_move_iterator(_Right._Unchecked_end()));
        }
    }

public:
    list& operator=(list&& _Right)
        _NOEXCEPT_COND(noexcept(_Move_assign(_Right, _Choose_pocma<_Alnode>{}))) { // partially strengthened
        if (this != _STD addressof(_Right)) { // different, assign it
            _Move_assign(_Right, _Choose_pocma<_Alnode>{});
        }

        return *this;
    }

private:
    void _Swap_val(list& _Right) noexcept { // swap with _Right, same allocator
        auto& _My_data    = _Get_data();
        auto& _Right_data = _Right._Get_data();
        _My_data._Swap_proxy_and_iterators(_Right_data);
        _Swap_adl(_My_data._Myhead, _Right_data._Myhead);
        _STD swap(_My_data._Mysize, _Right_data._Mysize);
    }

public:
    void push_front(_Ty&& _Val) { // insert element at beginning
        _Insert(_Unchecked_begin(), _STD move(_Val));
    }

    void push_back(_Ty&& _Val) { // insert element at end
        _Insert(_Unchecked_end(), _STD move(_Val));
    }

    iterator insert(const_iterator _Where, _Ty&& _Val) { // insert _Val at _Where
        return emplace(_Where, _STD move(_Val));
    }

    template <class... _Valty>
    decltype(auto) emplace_front(_Valty&&... _Val) { // insert element at beginning
        _Insert(_Unchecked_begin(), _STD forward<_Valty>(_Val)...);

#if _HAS_CXX17
        return front();
#endif // _HAS_CXX17
    }

    template <class... _Valty>
    decltype(auto) emplace_back(_Valty&&... _Val) { // insert element at end
        _Insert(_Unchecked_end(), _STD forward<_Valty>(_Val)...);

#if _HAS_CXX17
        return back();
#endif // _HAS_CXX17
    }

    template <class... _Valty>
    iterator emplace(const_iterator _Where, _Valty&&... _Val) { // insert element at _Where
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list emplace iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2

        _Insert(_Where._Unwrapped(), _STD forward<_Valty>(_Val)...);
        return _Make_iter(--_Where);
    }

    template <class... _Valty>
    void _Insert(_Unchecked_const_iterator _Where, _Valty&&... _Val) { // insert element at _Where
        size_type& _Mysize = _Get_data()._Mysize;
        if (_Mysize == max_size()) {
            _Xlength_error("list<T> too long");
        }

        _List_node_emplace_op<_Alnode, _Allocation_strategy::_Preallocated> _Op{_Getal()};
        _Op._Allocate(_STD forward<_Valty>(_Val)...);
        _Op._Transfer_before(_Where._Ptr);
        ++_Mysize;
    }

    list(initializer_list<_Ty> _Ilist) : _Mypair(_Zero_then_variadic_args_t()) { // construct from initializer_list
        _Construct_range_unchecked(_Ilist.begin(), _Ilist.end());
    }

    list(initializer_list<_Ty> _Ilist, const _Alloc& _Al)
        : _Mypair(_One_then_variadic_args_t(), _Al) { // construct from initializer_list, allocator
        _Construct_range_unchecked(_Ilist.begin(), _Ilist.end());
    }

    list& operator=(initializer_list<_Ty> _Ilist) { // assign initializer_list
        assign(_Ilist.begin(), _Ilist.end());
        return *this;
    }

    void assign(initializer_list<_Ty> _Ilist) { // assign initializer_list
        assign(_Ilist.begin(), _Ilist.end());
    }

    iterator insert(const_iterator _Where,
        initializer_list<_Ty> _Ilist) { // insert initializer_list
        return insert(_Where, _Ilist.begin(), _Ilist.end());
    }

    ~list() noexcept { // destroy the object
        _Tidy();
#if _ITERATOR_DEBUG_LEVEL != 0
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Delete_plain(_Alproxy, _Get_data()._Myproxy);
#endif /* _ITERATOR_DEBUG_LEVEL != 0 */
    }

private:
    void _Reload_sentinel_and_proxy(const list& _Right) { // reload sentinel / proxy from unequal POCCA _Right
        auto&& _Alproxy       = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        auto&& _Alproxy_right = _GET_PROXY_ALLOCATOR(_Alnode, _Right._Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy_right, _Leave_proxy_unbound{});
        auto _Alright = _Right._Getal();
        auto _Newhead = _Node::_Buyheadnode(_Alright);
        _Tidy();
        _Pocca(_Getal(), _Right._Getal());
        auto& _My_data   = _Get_data();
        _My_data._Myhead = _Newhead;
        _My_data._Mysize = 0;
        _Proxy._Bind(_Alproxy, _STD addressof(_My_data));
    }

    void _Copy_assign(const list& _Right, false_type) {
        _Pocca(_Getal(), _Right._Getal());
        assign(_Right._Unchecked_begin(), _Right._Unchecked_end());
    }

    void _Copy_assign(const list& _Right, true_type) {
        if (_Getal() != _Right._Getal()) {
            _Reload_sentinel_and_proxy(_Right);
        }

        assign(_Right._Unchecked_begin(), _Right._Unchecked_end());
    }

public:
    list& operator=(const list& _Right) { // assign _Right
        if (this != _STD addressof(_Right)) { // different, assign it
            _Copy_assign(_Right, _Choose_pocca<_Alnode>{});
        }

        return *this;
    }

    _NODISCARD iterator begin() noexcept { // return iterator for beginning of mutable sequence
        return iterator(_Myhead()->_Next, _STD addressof(_Get_data()));
    }

    _NODISCARD const_iterator begin() const noexcept { // return iterator for beginning of nonmutable sequence
        return const_iterator(_Myhead()->_Next, _STD addressof(_Get_data()));
    }

    _NODISCARD iterator end() noexcept { // return iterator for end of mutable sequence
        return iterator(_Myhead(), _STD addressof(_Get_data()));
    }

    _NODISCARD const_iterator end() const noexcept { // return iterator for end of nonmutable sequence
        return const_iterator(_Myhead(), _STD addressof(_Get_data()));
    }

    _Unchecked_iterator _Unchecked_begin() { // return iterator for beginning of mutable sequence
        return _Unchecked_iterator(_Myhead()->_Next, nullptr);
    }

    _Unchecked_const_iterator _Unchecked_begin() const { // return iterator for beginning of nonmutable sequence
        return _Unchecked_const_iterator(_Myhead()->_Next, nullptr);
    }

    _Unchecked_iterator _Unchecked_end() { // return unchecked iterator for end of mutable sequence
        return _Unchecked_iterator(_Myhead(), nullptr);
    }

    _Unchecked_const_iterator _Unchecked_end() const { // return unchecked iterator for end of nonmutable sequence
        return _Unchecked_const_iterator(_Myhead(), nullptr);
    }

    iterator _Make_iter(const_iterator _Where) const noexcept { // make iterator from const_iterator
        return iterator(_Where._Ptr, _STD addressof(_Get_data()));
    }

    iterator _Make_iter(_Unchecked_const_iterator _Where) const { // make iterator from _Unchecked_const_iterator
        return iterator(_Where._Ptr, _STD addressof(_Get_data()));
    }

    iterator _Make_iter(_Nodeptr _Where) const { // make iterator from node pointer
        return iterator(_Where, _STD addressof(_Get_data()));
    }

    const_iterator _Make_const_iter(_Unchecked_const_iterator _Where) const {
        // make const_iterator from _Unchecked_const_iterator
        return const_iterator(_Where._Ptr, _STD addressof(_Get_data()));
    }

    const_iterator _Make_const_iter(_Nodeptr _Where) const { // make const_iterator from node pointer
        return const_iterator(_Where, _STD addressof(_Get_data()));
    }

    _NODISCARD reverse_iterator rbegin() noexcept { // return iterator for beginning of reversed mutable sequence
        return reverse_iterator(end());
    }

    _NODISCARD const_reverse_iterator rbegin() const
        noexcept { // return iterator for beginning of reversed nonmutable sequence
        return const_reverse_iterator(end());
    }

    _NODISCARD reverse_iterator rend() noexcept { // return iterator for end of reversed mutable sequence
        return reverse_iterator(begin());
    }

    _NODISCARD const_reverse_iterator rend() const noexcept { // return iterator for end of reversed nonmutable sequence
        return const_reverse_iterator(begin());
    }

    _NODISCARD const_iterator cbegin() const noexcept { // return iterator for beginning of nonmutable sequence
        return begin();
    }

    _NODISCARD const_iterator cend() const noexcept { // return iterator for end of nonmutable sequence
        return end();
    }

    _NODISCARD const_reverse_iterator crbegin() const
        noexcept { // return iterator for beginning of reversed nonmutable sequence
        return rbegin();
    }

    _NODISCARD const_reverse_iterator crend() const
        noexcept { // return iterator for end of reversed nonmutable sequence
        return rend();
    }

    void resize(_CRT_GUARDOVERFLOW size_type _Newsize) { // determine new length, padding with _Ty() elements as needed
        auto& _My_data = _Get_data();
        if (_My_data._Mysize < _Newsize) { // pad to make larger
            _List_node_insert_op<_Alnode> _Op(_Getal());
            _Op._Append_n(_Newsize - _My_data._Mysize);
            _Op._Attach_at_end(_My_data);
        } else {
            while (_Newsize < _Mysize()) {
                pop_back();
            }
        }
    }

    void resize(_CRT_GUARDOVERFLOW size_type _Newsize, const _Ty& _Val) {
        // determine new length, padding with _Val elements as needed
        auto& _My_data = _Get_data();
        if (_My_data._Mysize < _Newsize) { // pad to make larger
            _List_node_insert_op<_Alnode> _Op(_Getal());
            _Op._Append_n(_Newsize - _My_data._Mysize, _Val);
            _Op._Attach_at_end(_My_data);
        } else {
            while (_Newsize < _Mysize()) {
                pop_back();
            }
        }
    }

    _NODISCARD size_type size() const noexcept { // return length of sequence
        return this->_Mysize();
    }

    _NODISCARD size_type max_size() const noexcept { // return maximum possible length of sequence
        return _Alnode_traits::max_size(_Getal());
    }

    _NODISCARD bool empty() const noexcept { // test if sequence is empty
        return _Mysize() == 0;
    }

    _NODISCARD allocator_type get_allocator() const noexcept { // return allocator object for values
        return static_cast<allocator_type>(_Getal());
    }

    _NODISCARD reference front() { // return first element of mutable sequence
        return *begin();
    }

    _NODISCARD const_reference front() const { // return first element of nonmutable sequence
        return *begin();
    }

    _NODISCARD reference back() { // return last element of mutable sequence
        return *(--end());
    }

    _NODISCARD const_reference back() const { // return last element of nonmutable sequence
        return *(--end());
    }

    void push_front(const _Ty& _Val) { // insert element at beginning
        _Insert(_Unchecked_begin(), _Val);
    }

    void pop_front() { // erase element at beginning
        _Unchecked_erase(_Unchecked_begin());
    }

    void push_back(const _Ty& _Val) { // insert element at end
        _Insert(_Unchecked_end(), _Val);
    }

    void pop_back() { // erase element at end
        _Unchecked_erase(--_Unchecked_end());
    }

private:
    template <class _Target_ref, class _UIter>
    void _Assign_cast(
        _UIter _UFirst, const _UIter _ULast) { // assign [_UFirst, _ULast), casting existing nodes to _Target_ref
        auto _Old         = _Unchecked_begin();
        const auto _Myend = _Unchecked_end();
        for (;;) { // attempt to reuse a node
            if (_Old == _Myend) { // no more nodes to reuse, append the rest
                _List_node_insert_op<_Alnode> _Op(_Getal());
                _Op._Append_range_unchecked(_UFirst, _ULast);
                _Op._Attach_at_end(_Get_data());
                return;
            }

            if (_UFirst == _ULast) {
                // input sequence was shorter than existing list, destroy and deallocate what's left
                _Unchecked_erase(_Old, _Myend);
                return;
            }

            // reuse the node
            reinterpret_cast<_Target_ref>(_Old._Ptr->_Myval) = *_UFirst;
            ++_Old;
            ++_UFirst;
        }
    }

public:
    template <class _Iter, class = enable_if_t<_Is_iterator_v<_Iter>>>
    void assign(_Iter _First, _Iter _Last) { // assign [_First, _Last)
        _Assign_cast<reference>(_Get_unwrapped(_First), _Get_unwrapped(_Last));
    }

    void assign(_CRT_GUARDOVERFLOW size_type _Count, const _Ty& _Val) { // assign _Count * _Val
        clear();
        _List_node_insert_op<_Alnode> _Op(_Getal());
        _Op._Append_n(_Count, _Val);
        _Op._Attach_at_end(_Get_data());
    }

    iterator insert(const_iterator _Where, const _Ty& _Val) { // insert _Val at _Where
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2

        _Insert(_Where._Unwrapped(), _Val);
        return _Make_iter(--_Where);
    }
    iterator insert(const_iterator _Where, _CRT_GUARDOVERFLOW size_type _Count,
        const _Ty& _Val) { // insert _Count * _Val before _Where
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        _List_node_insert_op<_Alnode> _Op(_Getal());
        _Op._Append_n(_Count, _Val);
        return _Make_iter(_Op._Attach_before(_Get_data(), _Where._Ptr));
    }

    template <class _Iter, class = enable_if_t<_Is_iterator_v<_Iter>>>
    iterator insert(const_iterator _Where, _Iter _First, _Iter _Last) { // insert [_First, _Last) before _Where
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list insert iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        _Adl_verify_range(_First, _Last);
        _List_node_insert_op<_Alnode> _Op(_Getal());
        _Op._Append_range_unchecked(_Get_unwrapped(_First), _Get_unwrapped(_Last));
        return _Make_iter(_Op._Attach_before(_Get_data(), _Where._Ptr));
    }

private:
    _Nodeptr _Unlinknode(_Unchecked_const_iterator _Where) { // unlink node at _Where from the list
        auto _Pnode = _Where._Ptr;
        _Orphan_ptr2(_Pnode);
        _Pnode->_Prev->_Next = _Pnode->_Next;
        _Pnode->_Next->_Prev = _Pnode->_Prev;
        --_Mysize();
        return _Pnode;
    }

    _Nodeptr _Unlinknode(const_iterator _Where) {
        return _Unlinknode(_Where._Unwrapped());
    }

    void _Relink(const _Unchecked_const_iterator _Where, const _Nodeptr _Ptr) { // Linkup _Ptr before _Where
        _Ptr->_Next        = _Where._Ptr;
        _Ptr->_Prev        = _Where._Ptr->_Prev;
        _Ptr->_Prev->_Next = _Ptr;
        _Ptr->_Next->_Prev = _Ptr;

        ++_Mysize();
    }

public:
    iterator erase(const_iterator _Where) { // erase element at _Where
#if _ITERATOR_DEBUG_LEVEL == 2
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list erase iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL == 2
        _Node::_Freenode(_Getal(), _Unlinknode(_Get_unwrapped(_Where++)));
        return _Make_iter(_Where);
    }

private:
    _Unchecked_iterator _Unchecked_erase(_Unchecked_const_iterator _Where) { // erase element at _Where
        _Nodeptr _Pnode = _Where._Ptr;
        _Unchecked_iterator _Result(_Pnode->_Next, nullptr);
        _Pnode->_Prev->_Next = _Pnode->_Next;
        _Pnode->_Next->_Prev = _Pnode->_Prev;
        _Node::_Freenode(_Getal(), _Pnode);
        --_Mysize();
        return _Result;
    }

public:
    iterator erase(const_iterator _First, const_iterator _Last) { // erase [_First, _Last)
        _Adl_verify_range(_First, _Last);
        return _Make_iter(_Unchecked_erase(_Get_unwrapped(_First), _Get_unwrapped(_Last)));
    }

private:
    _Unchecked_const_iterator _Unchecked_erase(
        _Unchecked_const_iterator _First, _Unchecked_const_iterator _Last) { // erase [_First, _Last)
        if (_First == _Unchecked_begin() && _Last == _Unchecked_end()) { // erase all and return fresh iterator
            clear();
            return _Unchecked_end();
        } else { // erase subrange
            while (_First != _Last) {
                _First = _Unchecked_erase(_First);
            }

            return _Last;
        }
    }

public:
    void clear() noexcept { // erase all
        auto& _My_data = _Get_data();
        _Orphan_non_end();
        _Node::_Free_non_head(_Getal(), _My_data._Myhead);
        _My_data._Myhead->_Next = _My_data._Myhead;
        _My_data._Myhead->_Prev = _My_data._Myhead;
        _My_data._Mysize        = 0;
    }

private:
    void _Tidy() noexcept {
        auto& _Al      = _Getal();
        auto& _My_data = _Get_data();
        _My_data._Orphan_all();
        _Node::_Free_non_head(_Al, _My_data._Myhead);
        _Node::_Freenode0(_Al, _My_data._Myhead);
    }

public:
    void swap(list& _Right) noexcept { // strengthened
        // exchange contents with _Right
        if (this != _STD addressof(_Right)) { // (maybe) swap allocators, swap control information
            _Pocs(_Getal(), _Right._Getal());
            _Swap_val(_Right);
        }
    }

    void splice(const_iterator _Where, list& _Right) { // splice all of _Right at _Where
        if (this != _STD addressof(_Right) && !_Right.empty()) { // worth splicing, do it
#if _ITERATOR_DEBUG_LEVEL != 0
            _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()), "list splice iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL != 0
            _Splice(_Where._Unwrapped(), _Right, _Right._Unchecked_begin(), _Right._Unchecked_end(), _Right._Mysize());
        }
    }

    void splice(const_iterator _Where, list&& _Right) { // splice all of _Right at _Where
        splice(_Where, _Right);
    }

    void splice(const_iterator _Where, list& _Right, const_iterator _First) {
        // splice _Right [_First, _First + 1) at _Where
#if _ITERATOR_DEBUG_LEVEL != 0
        _STL_VERIFY(
            _Where._Getcont() == _STD addressof(_Get_data()) && _First._Getcont() == _STD addressof(_Right._Get_data()),
            "list splice iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL != 0
        const _Unchecked_const_iterator _UWhere = _Where._Unwrapped();
        const _Unchecked_const_iterator _UFirst = _First._Unwrapped();

#if _ITERATOR_DEBUG_LEVEL == 2
        if (_UFirst == _Right._Unchecked_end()) {
            _STL_REPORT_ERROR("list splice iterator outside range");
        }
#endif // _ITERATOR_DEBUG_LEVEL == 2

        _Unchecked_const_iterator _ULast = _UFirst;
        ++_ULast;
        if (this != _STD addressof(_Right) || (_UWhere != _UFirst && _UWhere != _ULast)) {
            _Splice(_UWhere, _Right, _UFirst, _ULast, 1);
        }
    }

    void splice(const_iterator _Where, list&& _Right, const_iterator _First) {
        // splice _Right [_First, _First + 1) at _Where
        splice(_Where, _Right, _First);
    }

    void splice(const_iterator _Where, list& _Right, const_iterator _First, const_iterator _Last) {
        // splice _Right [_First, _Last) at _Where
#if _ITERATOR_DEBUG_LEVEL != 0
        const auto _Right_data_ptr = _STD addressof(_Right._Get_data());
        _STL_VERIFY(_Where._Getcont() == _STD addressof(_Get_data()) && _First._Getcont() == _Right_data_ptr
                        && _Last._Getcont() == _Right_data_ptr,
            "list splice iterator outside range");
#endif // _ITERATOR_DEBUG_LEVEL != 0

        const _Unchecked_const_iterator _UWhere = _Where._Unwrapped();
        const _Unchecked_const_iterator _UFirst = _First._Unwrapped();
        const _Unchecked_const_iterator _ULast  = _Last._Unwrapped();

        if (_UFirst != _ULast && (this != _STD addressof(_Right) || _UWhere != _ULast)) { // worth splicing, do it
            size_type _Count = 0;

            if (this != _STD addressof(_Right)) {
                const _Unchecked_const_iterator _Right_end = _Right._Unchecked_end();
                if (_UFirst == _Right._Unchecked_begin() && _ULast == _Right_end) {
                    _Count = _Right._Mysize(); // splice in whole list
                } else { // count nodes and check for knot
                    _Unchecked_const_iterator _Next = _UFirst;
                    for (; _Next != _ULast; ++_Next, (void) ++_Count) {
#if _ITERATOR_DEBUG_LEVEL != 0
                        _STL_VERIFY(_Next != _Right_end, "list<T> bad splice");
#endif // _ITERATOR_DEBUG_LEVEL != 0
                    }
                }
            }

            _Splice(_UWhere, _Right, _UFirst, _ULast, _Count);
        }
    }

    void splice(const_iterator _Where, list&& _Right, const_iterator _First, const_iterator _Last) {
        // splice _Right [_First, _Last) at _Where
        splice(_Where, _Right, _First, _Last);
    }

    auto remove(const _Ty& _Val) { // erase each element matching _Val
        auto _Val_it             = _Unchecked_end();
        const auto _Last         = _Unchecked_end();
        const size_type _Oldsize = _Mysize();

        for (auto _First = _Unchecked_begin(); _First != _Last;) {
            if (*_First == _Val) {
                if (_STD addressof(*_First) == _STD addressof(_Val)) {
                    _Val_it = _First++;
                } else {
                    _First = _Unchecked_erase(_First);
                }
            } else {
                ++_First;
            }
        }

        if (_Val_it != _Last) {
            _Unchecked_erase(_Val_it);
        }

#if _HAS_CXX20
        return _Oldsize - _Mysize();
#else // _HAS_CXX20
        (void) _Oldsize;
#endif // _HAS_CXX20
    }

    template <class _Pr1>
    auto remove_if(_Pr1 _Pred) { // erase each element satisfying _Pred
        const auto _Last         = _Unchecked_end();
        const size_type _Oldsize = _Mysize();
        for (auto _First = _Unchecked_begin(); _First != _Last;) {
            if (_Pred(*_First)) {
                _First = _Unchecked_erase(_First);
            } else {
                ++_First;
            }
        }

#if _HAS_CXX20
        return _Oldsize - _Mysize();
#else // _HAS_CXX20
        (void) _Oldsize;
#endif // _HAS_CXX20
    }

    auto unique() { // erase each element matching previous
        return unique(equal_to<>());
    }

    template <class _Pr2>
    auto unique(_Pr2 _Pred) { // erase each element satisfying _Pred with previous
        const _Nodeptr _Phead    = _Myhead();
        _Nodeptr _Pprev          = _Phead->_Next;
        _Nodeptr _Pnode          = _Pprev->_Next;
        const size_type _Oldsize = _Mysize();
        while (_Pnode != _Phead) {
            if (_Pred(_Pprev->_Myval, _Pnode->_Myval)) { // match, remove it
                const _Nodeptr _Perase = _Pnode;
                _Pnode                 = _Pnode->_Next;
                _Orphan_ptr2(_Perase);
                _Pprev->_Next = _Pnode;
                _Pnode->_Prev = _Pprev;
                _Node::_Freenode(_Getal(), _Perase);

                --_Mysize();
            } else { // no match, advance
                _Pprev = _Pnode;
                _Pnode = _Pnode->_Next;
            }
        }

#if _HAS_CXX20
        return _Oldsize - _Mysize();
#else // _HAS_CXX20
        (void) _Oldsize;
#endif // _HAS_CXX20
    }

    void merge(list& _Right) { // merge in elements from _Right, both ordered by operator<
        _Merge1(_Right, less<>());
    }

    void merge(list&& _Right) { // merge in elements from _Right, both ordered by operator<
        _Merge1(_Right, less<>());
    }

    template <class _Pr2>
    void merge(list& _Right, _Pr2 _Pred) { // merge in elements from _Right, both ordered by _Pred
        _Merge1(_Right, _Pass_fn(_Pred));
    }

    template <class _Pr2>
    void merge(list&& _Right, _Pr2 _Pred) { // merge in elements from _Right, both ordered by _Pred
        _Merge1(_Right, _Pass_fn(_Pred));
    }

private:
    template <class _Pr2>
    void _Merge1(list& _Right, _Pr2 _Pred) { // merge in elements from _Right, both ordered by _Pred
        if (this == _STD addressof(_Right)) {
            return;
        }

        // safe to merge, do it
        auto _First1 = _Unchecked_begin();
        auto _Last1  = _Unchecked_end();
        _DEBUG_ORDER_UNWRAPPED(_First1, _Last1, _Pred);

        auto _First2 = _Right._Unchecked_begin();
        auto _Last2  = _Right._Unchecked_end();
        _DEBUG_ORDER_UNWRAPPED(_First2, _Last2, _Pred);

        while (_First1 != _Last1 && _First2 != _Last2) {
            if (_Pred(*_First2, *_First1)) { // splice in an element from _Right
                auto _Oldfirst2 = _First2;
                _Splice(_First1, _Right, _Oldfirst2, ++_First2, 1);
            } else {
                ++_First1;
            }
        }

        if (_First2 != _Last2) {
            _Splice(_Last1, _Right, _First2, _Last2, _Right._Mysize()); // splice remainder of _Right
        }
    }

public:
    void sort() { // order sequence, using operator<
        sort(less<>());
    }

    template <class _Pr2>
    void sort(_Pr2 _Pred) { // order sequence, using _Pred
        _Sort(begin(), end(), _Pass_fn(_Pred), _Mysize());
    }

private:
    template <class _Pr2>
    iterator _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return _First; // nothing to do
        }

        iterator _Mid      = _STD next(_First, static_cast<difference_type>(_Size >> 1));
        _First             = _Sort(_First, _Mid, _Pred, _Size >> 1);
        _Mid               = _Sort(_Mid, _Last, _Pred, _Size - (_Size >> 1));
        iterator _Newfirst = _First;

        for (bool _Initial_loop = true;;
             _Initial_loop      = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }

                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            } else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

public:
    void reverse() noexcept { // reverse sequence
        const _Nodeptr _Phead = _Myhead();
        _Nodeptr _Pnode       = _Phead;

        for (;;) { // flip pointers in a node
            const _Nodeptr _Pnext = _Pnode->_Next;
            _Pnode->_Next         = _Pnode->_Prev;
            _Pnode->_Prev         = _Pnext;

            if (_Pnext == _Phead) {
                break;
            }

            _Pnode = _Pnext;
        }
    }

private:
    void _Splice(_Unchecked_const_iterator _Where, list& _Right, _Unchecked_const_iterator _First,
        _Unchecked_const_iterator _Last, size_type _Count) {
        // splice _Right [_First, _Last) before _Where
        if (this != _STD addressof(_Right)) { // splicing from another list, adjust counts
            if (max_size() - _Mysize() < _Count) {
                _Xlength_error("list<T> too long");
            }

            _Mysize() += _Count;
            _Right._Mysize() -= _Count;
        }

#if _ITERATOR_DEBUG_LEVEL == 2
        if
            _CONSTEXPR_IF(!_Alnode_traits::is_always_equal::value) {
                _STL_VERIFY(_Getal() == _Right._Getal(), "list containers incompatible for splice");
            }

        if (this != _STD addressof(_Right)) { // transfer ownership
            _Lockit _Lock(_LOCK_DEBUG);
            _Iterator_base12** _Pnext = &_Right._Get_data()._Myproxy->_Myfirstiter;
            const auto _Myproxy       = _Get_data()._Myproxy;
            const auto _Righthead     = _Right._Myhead();

            if (_Count == 1) { // adopt iterators pointing to the spliced element
                while (*_Pnext != nullptr) {
                    auto& _Iter = static_cast<const_iterator&>(**_Pnext);
                    if (_Iter._Ptr == _First._Ptr) { // adopt the iterator
                        *_Pnext                = _Iter._Mynextiter;
                        _Iter._Myproxy         = _Myproxy;
                        _Iter._Mynextiter      = _Myproxy->_Myfirstiter;
                        _Myproxy->_Myfirstiter = _STD addressof(_Iter);
                    } else { // skip the iterator
                        _Pnext = &_Iter._Mynextiter;
                    }
                }
            } else if (_Count == _Right.size()) { // adopt all iterators except _Right.end()
                while (*_Pnext != nullptr) {
                    auto& _Iter = static_cast<const_iterator&>(**_Pnext);
                    if (_Iter._Ptr != _Righthead) { // adopt the iterator
                        *_Pnext                = _Iter._Mynextiter;
                        _Iter._Myproxy         = _Myproxy;
                        _Iter._Mynextiter      = _Myproxy->_Myfirstiter;
                        _Myproxy->_Myfirstiter = _STD addressof(_Iter);
                    } else { // skip the iterator
                        _Pnext = &_Iter._Mynextiter;
                    }
                }
            } else { // mark spliced elements and adopt iterators to marked elements
                _Nodeptr _Oldprev = _First._Ptr->_Prev;
                for (_Nodeptr _Ptr = _First._Ptr; _Ptr != _Last._Ptr; _Ptr = _Ptr->_Next) { // mark _Prev pointers
                    _Ptr->_Prev = nullptr;
                }

                while (*_Pnext != nullptr) { // check the iterator
                    auto& _Iter = static_cast<const_iterator&>(**_Pnext);
                    if (_Iter._Ptr->_Prev == nullptr) { // adopt the iterator
                        *_Pnext                = _Iter._Mynextiter;
                        _Iter._Myproxy         = _Myproxy;
                        _Iter._Mynextiter      = _Myproxy->_Myfirstiter;
                        _Myproxy->_Myfirstiter = _STD addressof(_Iter);
                    } else { // skip the iterator
                        _Pnext = &_Iter._Mynextiter;
                    }
                }

                for (_Nodeptr _Ptr = _First._Ptr; _Ptr != _Last._Ptr; _Ptr = _Ptr->_Next) { // restore _Prev pointers
                    _Ptr->_Prev = _Oldprev;
                    _Oldprev    = _Ptr;
                }
            }
        }

#else // _ITERATOR_DEBUG_LEVEL == 2
        if
            _CONSTEXPR_IF(!_Alnode_traits::is_always_equal::value) {
                if (_Getal() != _Right._Getal()) {
                    _STD terminate();
                }
            }
#endif // _ITERATOR_DEBUG_LEVEL == 2

        _First._Ptr->_Prev->_Next = _Last._Ptr;
        _Last._Ptr->_Prev->_Next  = _Where._Ptr;
        _Where._Ptr->_Prev->_Next = _First._Ptr;

        _Nodeptr _Pnode    = _Where._Ptr->_Prev;
        _Where._Ptr->_Prev = _Last._Ptr->_Prev;
        _Last._Ptr->_Prev  = _First._Ptr->_Prev;
        _First._Ptr->_Prev = _Pnode;
    }

    void _Unchecked_splice(
        _Unchecked_const_iterator _Before, _Unchecked_const_iterator _First, _Unchecked_const_iterator _Last) {
        // splice [_First, _Last) before _Before
        _First._Ptr->_Prev->_Next  = _Last._Ptr;
        _Last._Ptr->_Prev->_Next   = _Before._Ptr;
        _Before._Ptr->_Prev->_Next = _First._Ptr;

        _Nodeptr _Pnode     = _Before._Ptr->_Prev;
        _Before._Ptr->_Prev = _Last._Ptr->_Prev;
        _Last._Ptr->_Prev   = _First._Ptr->_Prev;
        _First._Ptr->_Prev  = _Pnode;
    }

    // _Orphan_ptr is an ABI zombie name
    void _Orphan_ptr2(_Nodeptr _Ptr) noexcept { // orphan iterators with specified node pointers
#if _ITERATOR_DEBUG_LEVEL == 2
        _Lockit _Lock(_LOCK_DEBUG);
        _Iterator_base12** _Pnext = &_Get_data()._Myproxy->_Myfirstiter;
        const auto _Head          = _Myhead();
        while (*_Pnext != nullptr) {
            _Iterator_base12** _Pnextnext = &(*_Pnext)->_Mynextiter;
            const auto _Pnextptr          = static_cast<const_iterator&>(**_Pnext)._Ptr;
            if (_Pnextptr == _Head || _Pnextptr != _Ptr) {
                // iterator is end() or doesn't point at the one we are orphaning, move on
                _Pnext = _Pnextnext;
            } else { // orphan the iterator
                (*_Pnext)->_Myproxy = nullptr;
                *_Pnext             = *_Pnextnext;
            }
        }
#else // ^^^ _ITERATOR_DEBUG_LEVEL == 2 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 2 vvv
        (void) _Ptr;
#endif // _ITERATOR_DEBUG_LEVEL == 2
    }

    void _Orphan_non_end() noexcept { // orphan iterators except end()
#if _ITERATOR_DEBUG_LEVEL == 2
        _Lockit _Lock(_LOCK_DEBUG);
        _Iterator_base12** _Pnext = &_Get_data()._Myproxy->_Myfirstiter;
        const auto _Head          = _Myhead();
        while (*_Pnext != nullptr) {
            _Iterator_base12** _Pnextnext = &(*_Pnext)->_Mynextiter;
            if (static_cast<const_iterator&>(**_Pnext)._Ptr == _Head) { // iterator is end(), move on
                _Pnext = _Pnextnext;
            } else { // orphan the iterator
                (*_Pnext)->_Myproxy = nullptr;
                *_Pnext             = *_Pnextnext;
            }
        }
#endif // _ITERATOR_DEBUG_LEVEL == 2
    }

    void _Alloc_sentinel_and_proxy() {
        auto& _My_data  = _Get_data();
        auto&& _Alproxy = _GET_PROXY_ALLOCATOR(_Alnode, _Getal());
        _Container_proxy_ptr<_Alty> _Proxy(_Alproxy, _My_data);
        auto& _Al     = _Getal();
        auto _Newhead = _Al.allocate(1);
        _Alnode_traits::construct(_Al, _STD addressof(_Newhead->_Next), _Newhead); // assumed nothrow
        _Alnode_traits::construct(_Al, _STD addressof(_Newhead->_Prev), _Newhead);
        _My_data._Myhead = _Newhead;
        _Proxy._Release();
    }

    void _Freeheadnode(_Nodeptr _Pnode) { // free head node using current allocator
        _Node::_Freenode0(_Getal(), _Pnode);
    }

    void _Orphan_all() { // orphan all iterators
        _Get_data()._Orphan_all();
    }

    _Alnode& _Getal() noexcept { // return reference to allocator
        return _Mypair._Get_first();
    }

    const _Alnode& _Getal() const noexcept { // return const reference to allocator
        return _Mypair._Get_first();
    }

    _Scary_val& _Get_data() noexcept { // return reference to _Scary_val
        return _Mypair._Myval2;
    }

    const _Scary_val& _Get_data() const noexcept { // return const reference to _Scary_val
        return _Mypair._Myval2;
    }

    _Nodeptr& _Myhead() noexcept { // return reference to _Myhead
        return _Get_data()._Myhead;
    }

    const _Nodeptr& _Myhead() const noexcept { // return const reference to _Myhead
        return _Get_data()._Myhead;
    }

    size_type& _Mysize() noexcept { // return reference to _Mysize
        return _Get_data()._Mysize;
    }

    const size_type& _Mysize() const noexcept { // return const reference to _Mysize
        return _Get_data()._Mysize;
    }

    _Compressed_pair<_Alnode, _Scary_val> _Mypair;
};

#if _HAS_CXX17
template <class _Iter, class _Alloc = allocator<_Iter_value_t<_Iter>>,
    enable_if_t<conjunction_v<_Is_iterator<_Iter>, _Is_allocator<_Alloc>>, int> = 0>
list(_Iter, _Iter, _Alloc = _Alloc())->list<_Iter_value_t<_Iter>, _Alloc>;
#endif // _HAS_CXX17

template <class _Ty, class _Alloc>
inline void swap(list<_Ty, _Alloc>& _Left, list<_Ty, _Alloc>& _Right) noexcept { // strengthened
    // swap _Left and _Right lists
    _Left.swap(_Right);
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator==(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test for list equality
    return _Left.size() == _Right.size() && _STD equal(_Left.begin(), _Left.end(), _Right.begin());
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator!=(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test for list inequality
    return !(_Left == _Right);
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator<(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test if _Left < _Right for lists
    return _STD lexicographical_compare(_Left.begin(), _Left.end(), _Right.begin(), _Right.end());
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator>(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test if _Left > _Right for lists
    return _Right < _Left;
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator<=(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test if _Left <= _Right for lists
    return !(_Right < _Left);
}

template <class _Ty, class _Alloc>
_NODISCARD inline bool operator>=(
    const list<_Ty, _Alloc>& _Left, const list<_Ty, _Alloc>& _Right) { // test if _Left >= _Right for lists
    return !(_Left < _Right);
}

#if _HAS_CXX17
namespace pmr {
    template <class _Ty>
    using list = _STD list<_Ty, polymorphic_allocator<_Ty>>;
} // namespace pmr
#endif // _HAS_CXX17
_STD_END
#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _LIST_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
